package hot100;

/**
 * @author 江岸
 * @version V1.0
 * @ClassName: FindMedianSortedArrays4
 * @description: 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数。
 *
 * 进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @date 2021/2/2517:21
 * @since V1.0
 */
public class FindMedianSortedArrays4 {
    public static void main(String[] args) {
        int[] nums1 = {};
        int[] nums2 = {1};
        findMedianSortedArrays(nums1,nums2);
    }

    //双指针
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        if (nums1.length==0){
            return fun(nums2);
        }
        if (nums2.length==0){
            return fun(nums1);
        }
        int i=0;
        int j=0;
        int n=0;
        int[] arr = new int[nums1.length + nums2.length];
        while (i<nums1.length || j<nums2.length){
            if (nums1[i]<nums2[j]){
                arr[n] = nums1[i];
                i++;
                if (i==nums1.length){
                    for (int x=j;x< nums2.length;x++){
                        arr[++n] = nums2[x];
                    }
                    break;
                }
            }else {
                arr[n] = nums2[j];
                j++;
                if (j==nums2.length){
                    for (int x=i;x<nums1.length;x++){
                        arr[++n] = nums1[x];
                    }
                    break;
                }
            }
            n++;
        }
        return fun(arr);
    }
    public static double fun(int[] arr){
        if ((arr.length&1)==1){
            //基数长度
            return (double) arr[(arr.length-1)/2];
        }else {
            //偶数长度
            return  (double) (arr[arr.length/2 - 1]+ arr[arr.length/2])/2;
        }
    }

    //二分查找
    /**
     * 根据中位数的定义，当 m+nm+nm+n 是奇数时，中位数是两个有序数组中的第 (m+n)/2(m+n)/2(m+n)/2 个元素，当 m+nm+nm+n 是偶数时，
     * 中位数是两个有序数组中的第 (m+n)/2(m+n)/2(m+n)/2 个元素和第 (m+n)/2+1(m+n)/2+1(m+n)/2+1 个元素的平均值。
     * 因此，这道题可以转化成寻找两个有序数组中的第 kkk 小的数，其中 kkk 为 (m+n)/2(m+n)/2(m+n)/2 或 (m+n)/2+1(m+n)/2+1(m+n)/2+1。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    public double 官方题解(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int m = nums2.length;
        int left = (n + m + 1) / 2;
        int right = (n + m + 2) / 2;
        //将偶数和奇数的情况合并，如果是奇数，会求两次同样的 k 。
        return (getKth(nums1, 0, n - 1, nums2, 0, m - 1, left) + getKth(nums1, 0, n - 1, nums2, 0, m - 1, right)) * 0.5;
    }


    private int getKth(int[] nums1, int start1, int end1, int[] nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        //让 len1 的长度小于 len2，这样就能保证如果有数组空了，一定是 len1
        if (len1 > len2) return getKth(nums2, start2, end2, nums1, start1, end1, k);
        if (len1 == 0) return nums2[start2 + k - 1];

        if (k == 1) return Math.min(nums1[start1], nums2[start2]);

        int i = start1 + Math.min(len1, k / 2) - 1;
        int j = start2 + Math.min(len2, k / 2) - 1;

        if (nums1[i] > nums2[j]) {
            return getKth(nums1, start1, end1, nums2, j + 1, end2, k - (j - start2 + 1));
        }
        else {
            return getKth(nums1, i + 1, end1, nums2, start2, end2, k - (i - start1 + 1));
        }
    }

}
